#include <iostream>
#include <vector>
using namespace std;
class MergeSorter {
private:
	void merge(vector<int>& nums, int left, int mid, int right) {
		vector<int>temp(right - left + 1);
		int i = left;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= right) {
			if (nums[i] <= nums[j]) {
				temp[k] = nums[i];
				i++;
			}
			else {
				temp[k] = nums[j++];
			}
			k++;
		}
		while (i <= mid) { temp[k++] = nums[i++]; }
		while (j <= right) { temp[k++] = nums[j++]; }
		for (int a = 0; a <k; a++) {
			nums[left + a] = temp[a];
		}
	}
public:
	void sorthelper(vector<int>&nums,int left, int right) {
		if (left >= right)return;
		int mid = left+(right - left) / 2;
		sorthelper(nums,left, mid);
		sorthelper(nums,mid+1, right);
		merge(nums, left, mid, right);
	}
};